package com.south.base.test.arithmetic;

import org.junit.Assert;
import org.junit.Test;

/**
 * @author Administrator
 * @date 2020/6/8 17:20
 */
public class EquationsPossible {
    /**
     * 给定一个由表示变量之间关系的字符串方程组成的数组，
     * 每个字符串方程 equations[i] 的长度为 4，
     * 并采用两种不同的形式之一："a==b" 或 "a!=b"。
     * 在这里，a 和 b 是小写字母（不一定不同），表示单字母变量名。
     * 只有当可以将整数分配给变量名，以便满足所有给定的方程时才返回 true，否则返回 false。 
     */
    @Test
    public void equationsPossible() {
        Assert.assertFalse(equationsPossible(new String[]{"a==b", "b==c", "d==e", "e==f", "d==a", "f!=a"}));
        Assert.assertFalse(equationsPossible(new String[]{"a!=a"}));
        Assert.assertFalse(equationsPossible(new String[]{"a==b", "b!=a"}));
        Assert.assertFalse(equationsPossible(new String[]{"a==b", "b!=c", "c==a"}));
        Assert.assertTrue(equationsPossible(new String[]{"c==c", "b==d", "x!=z"}));
        Assert.assertTrue(equationsPossible(new String[]{"b==a", "a==b"}));
        Assert.assertTrue(equationsPossible(new String[]{"a==b", "b==c", "a==c"}));
        Assert.assertTrue(equationsPossible(new String[]{"c==c", "f!=a", "f==b", "b==c"}));
    }

    public boolean equationsPossible(String[] equations) {
        Object[] arr = new Object[26];
        for (String equation : equations) {
            char c = equation.charAt(1);
            int indexA = equation.charAt(0) - 'a';
            int indexB = equation.charAt(equation.length() - 1) - 'a';
            if (c == '=') {
                Object node = null;
                if (arr[indexA] != null) {
                    node = arr[indexA];
                }
                if (arr[indexB] != null) {
                    node = arr[indexB];
                }
                if (node == null) {
                    node = new Object();
                }
                Object t1 = arr[indexA];
                Object t2 = arr[indexB];
                for (int i = 0; i < arr.length; i++) {
                    if (arr[i] != null && (arr[i] == t1 || arr[i] == t2)) {
                        arr[i] = node;
                    }
                }
                arr[indexA] = arr[indexB] = node;
            }
        }
        for (String equation : equations) {
            char c = equation.charAt(1);
            int indexA = equation.charAt(0) - 'a';
            int indexB = equation.charAt(equation.length() - 1) - 'a';
            if (c == '!') {
                if (arr[indexA] != null && arr[indexB] != null && arr[indexA] == arr[indexB]) {
                    return false;
                }
                if (indexA == indexB) {
                    return false;
                }
                if (arr[indexA] == null) {
                    arr[indexA] = new Object();
                }
                if (arr[indexB] == null) {
                    arr[indexB] = new Object();
                }
            }
        }
        return true;
    }
}
